package code.oldCode.dynamic;

/**
 * @author cuihaoran
 * @date 2024/10/15
 */
public class BackPack {

    /**
     * 279. 完全平方数
     *
     * @param n
     * @return
     */
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            // 计算dp[i]
            int min = Integer.MAX_VALUE;
            for (int j = 1; j <= Math.sqrt(i); j++) {
                min = Math.min(min, dp[i - j * j]);
            }
            dp[i] = 1 + min;
        }
        return dp[n];
    }

    /**
     * 518. 零钱兑换 II
     *
     * @param amount
     * @param coins
     * @return
     */
    public int change(int amount, int[] coins) {
        // amount = 5, coins = [1, 2, 5]
        // dp[1] = 1    [1]
        // dp[2] = 2    [1,1],[2]
        // dp[3] = 2    [1,1,1],[1,2]
        // dp[4] = 3    [1,1,1,1],[1,1,2],[2,2]
        // dp[5] = 4    [1,1,1,1,1],[1,1,1,2],[1,2,2],[5]
        // dp[i]表示对于amount=i时能凑的组合数。长度为容量+1
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        // 注意外循环为coins内循环为amount，与爬楼梯(70)问题正好相反
        // 因为爬楼梯(70)问题是求排列数(112和121不一样)，本题是求组合数(112和121一样)

        // 组合数：先遍历物品
        for (Integer coin : coins) {
            // 组合数：再遍历容量
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }

    /**
     * 原始写法
     */
    public int change_(int amount, int[] coins) {
        // DP[k][i]表示前k个硬币凑齐金额i的组合数
        int len = coins.length;
        int[][] DP = new int[len + 1][amount + 1];
        for (int k = 0; k < len; k++) {
            DP[k][0] = 1;
        }
        // 用前k个硬币
        for (int k = 1; k <= len; k++) {
            // 凑齐金额i
            for (int i = 1; i <= amount; i++) {
                if (i >= coins[k - 1])
                    DP[k][i] = DP[k][i - coins[k - 1]] + DP[k - 1][i];
                else
                    DP[k][i] = DP[k - 1][i];
            }
        }

        return DP[len][amount];
    }

    /**
     * 322. 零钱兑换 (bonus)
     *
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange(int[] coins, int amount) {
        // ！！！集齐某金额的最小数量！！！
        // dp[a]表示集齐金额a所需最少硬币数量
        int[] dp = new int[amount + 1];
        dp[0] = 0;
        for (int a = 1; a <= amount; a++) {
            dp[a] = Integer.MAX_VALUE;
            for (int coin : coins) {
                if (a >= coin && dp[a - coin] != -1)
                    dp[a] = Math.min(dp[a], dp[a - coin] + 1);
            }
            if (dp[a] == Integer.MAX_VALUE)
                dp[a] = -1;
        }

        return dp[amount];
    }

    /**
     * 377. 组合总和 Ⅳ
     *
     * @param nums
     * @param target
     * @return
     */
    public int combinationSum4(int[] nums, int target) {
        // 这个和70.爬楼梯本质是一样的，只不过楼梯能爬1或2步，这个能爬nums[0~len-1]步
        // dp[t] = sum(dp[t - nums[0~i-1]])
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int t = 1; t <= target; t++) {
            for (Integer num : nums) {
                if (num <= t) {
                    dp[t] += dp[t - num];
                }
            }
        }

        return dp[target];
    }

    /**
     * 474. 一和零
     *
     * @param strs
     * @param m
     * @param n
     * @return
     */
    public int findMaxForm(String[] strs, int m, int n) {
        // ！！！不超过某金额的最大数量！！！
        // 找strs的最大子集长度，要求子集最多有m个0和n个1
        // dp[i][j]表示子集最多有i个0和j个1的最大子集长度
        // dp[i][j] = max(dp[i - strs[0~k-1] of 0][j - strs[0~k-1] of 1])
        int[][] dp = new int[m + 1][n + 1];
        // dp 先遍历物品，再遍历容量
        dp[0][0] = 0;
        for (String s : strs) {
            int[] num_01 = find01Num(s);
            // !!!倒着循环!!!因为dp要与上一次的dp对比，倒着这样保证dp更新的先后顺序
            // 本质上是因为我省略了一维，dp[][][]的话就没这个问题了
            for (int i = m; i >= num_01[0]; i--) {
                for (int j = n; j >= num_01[1]; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - num_01[0]][j - num_01[1]] + 1);
                }
            }
        }
        return dp[m][n];
    }

    public int[] find01Num(String s) {
        int num_0 = 0, num_1 = 0;
        char[] charArray = s.toCharArray();
        for (Character c : charArray) {
            if (c == '1') num_1++;
            else if (c == '0') num_0++;
        }
        return new int[]{num_0, num_1};
    }

    public static void main(String[] args) {
        BackPack backPack = new BackPack();
        String[] strs = new String[]{"10", "0001", "111001", "1", "0"};
        System.out.println(backPack.findMaxForm(strs, 5, 3));
    }
}
